﻿#region GPLv2 license (Confirmation required, contact joxonproductions@gmail.com if source is found)
/*
Copyright (C) 2009-2010 Jamm Daemon project <http://code.google.com/p/jammd/>

Jamm is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
*/
#endregion

using System;
using System.Collections.Generic;
using System.Collections;

namespace Jamm.SharedLib.Math
{
    /// <summary>
    /// BigNumber class
    /// </summary>
    public class BigNumber
    {
        private readonly List<int> Digits = new List<int>();
        private readonly Hashtable HT = new Hashtable();
        /// <summary>
        /// Reminder of division operation: A / B = C + DivReminder
        /// </summary>
        public BigNumber DivReminder;
        /// <summary>
        /// Reminder of square root: Sqrt(A) = B + SqrtReminder
        /// </summary>
        private bool IsNegative = false;

        /// <summary>
        /// Value representing zero value
        /// </summary>
        public static BigNumber Zero = new BigNumber(0);
        /// <summary>
        /// Value representing an undefined number. 
        /// </summary>
        public static BigNumber Nothing = new BigNumber();

        /// <summary>
        /// Digit count of a number.
        /// </summary>
        public int Length { get { return Digits.Count; } }

        private void BigNumberInit(string nr)
        {
            int i;
            string n;

            for (i = 0; i < 10; i++) { HT.Add(i.ToString(), i); }

            for (i = 0; i < nr.Length; i++)
            {
                n = nr.Substring(nr.Length - 1 - i, 1);
                if (HT.Contains(n))
                {
                    //if(!(Digits.Count==nr.Length-1 && n=="0")) 
                    Digits.Add((int)HT[n]);
                }
                else
                {
                    IsNegative = (n == "-");
                }
            }

        }

        /// <summary>
        /// Creates a Big Number from a string containig digits
        /// </summary>
        /// <param name="nr">String representation of a number. For example - "1234567890"</param>
        public BigNumber(string nr) { BigNumberInit(nr); }
        /// <summary>
        /// Creates a Big Number from an integer value
        /// </summary>
        /// <param name="nr">Integer reporesentation of a number. For example - 1234567890</param>
        public BigNumber(int nr) { BigNumberInit(nr.ToString()); }
        /// <summary>
        /// Creates a Big Number based on another Big Number.
        /// </summary>
        /// <param name="nr">Previously defined BigNumber instance</param>
        public BigNumber(BigNumber nr) { BigNumberInit(nr.ToString()); }
        /// <summary>
        /// Creates a Big Number with undefined value. This is usefull when constructing a number using an algorythm. You should never proceed with arithmetic operations with an undefined number.
        /// </summary>
        public BigNumber() { BigNumberInit(""); }

        /// <summary>
        /// String representation of Big Number
        /// </summary>
        /// <returns>A string representing array of digits in the number</returns>
        public override string ToString()
        {
            string r = (IsNegative ? "-" : "") + (Digits.Count > 0 ? "" : "0");

            for (int i = Digits.Count; i > 0; i--) r += Digits[i - 1];

            return r;
        }

        /// <summary>
        /// Verifies if current BigNumber is equal to given object.
        /// </summary>
        /// <param name="obj">An object to compare to cuttent BigNumber</param>
        /// <returns>True or false</returns>
        public override bool Equals(object obj)
        {
            return base.Equals(obj);
        }

        /// <summary>
        /// Retrieves a hash code for current object
        /// </summary>
        /// <returns>An unique integer hash code</returns>
        public override int GetHashCode()
        {
            return base.GetHashCode();
        }

        /// <summary>
        /// Duplicates current Big Number to another instance
        /// </summary>
        /// <returns>Clone of a current Big Number</returns>
        public BigNumber Clone()
        {
            return (new BigNumber(this.ToString()));
        }

        /// <summary>
        /// Retrieves an absolute value of a number
        /// </summary>
        /// <returns>Absolute value</returns>
        public BigNumber Abs()
        {
            BigNumber R = this.Clone();
            R.IsNegative = false;

            return R;
        }

        /// <summary>
        /// Subtract two numbers
        /// </summary>
        /// <param name="A">Number to subtract from</param>
        /// <param name="B">Number to substract</param>
        /// <returns>A-B</returns>
        public static BigNumber operator -(BigNumber A, BigNumber B)
        {

            int i, rem = 0, r;
            string res = "";
            BigNumber R, X, Y;
            bool Neg = false;

            if (!B) { return (new BigNumber(A)); }

            if (A.IsNegative && !B.IsNegative) { R = B + A.Abs(); return new BigNumber("-" + R.ToString()); }
            if (A.IsNegative && B.IsNegative) { R = B.Abs() - A.Abs(); return new BigNumber(R); }
            if (!A.IsNegative && B.IsNegative) { return new BigNumber(A + B.Abs()); }

            if (A.Digits.Count < B.Digits.Count) Neg = true;
            if (A.Digits.Count == B.Digits.Count)
            {
                for (i = A.Digits.Count - 1; i >= 0; i--)
                {
                    if (A.Digits[i] < B.Digits[i]) { Neg = true; break; }
                    if (A.Digits[i] > B.Digits[i]) break;
                }
            }

            if (Neg)
            {
                X = B; Y = A;
            }
            else
            {
                X = A; Y = B;
            }

            for (i = 0; i < X.Digits.Count; i++)
            {
                r = (Y.Digits.Count > i ? Y.Digits[i] : 0);
                r = X.Digits[i] - rem - r;
                rem = (r < 0 ? 1 : 0);
                res = (r < 0 ? (r + 10) : r) + res;
            }

            res = res.TrimStart('0');

            if (rem == 1) { throw new Exception("Reminder left on Sub! This should not have happened!"); }

            R = new BigNumber((Neg ? "-" : "") + res);
            return R;
        }

        /// <summary>
        /// Increases given number by one.
        /// </summary>
        /// <param name="A">Number to increase</param>
        /// <returns>Increased number</returns>
        public static BigNumber operator ++(BigNumber A)
        {
            int i, rem = 1;
            int[] newdig;

            newdig = (int[])(A.Digits.ToArray());

            for (i = 0; i < newdig.Length; i++)
            {
                newdig[i] += rem;
                if (newdig[i] > 9) { newdig[i] -= 10; rem = 1; }
                else { rem = 0; break; }
            }

            A.Digits.Clear();
            A.Digits.AddRange(newdig);

            if (rem == 1) A.Digits.Add(1);

            return A;
        }

        /// <summary>
        /// Decreases a number by one.
        /// </summary>
        /// <param name="A">Number to decrease</param>
        /// <returns>Decreased number</returns>
        public static BigNumber operator --(BigNumber A)
        {
            return (A - (new BigNumber(1)));
        }

        /// <summary>
        /// Boolean representation of a number: If number is undefined or zero, it is considered false.
        /// </summary>
        /// <param name="A">Number to check</param>
        /// <returns>True or false</returns>
        public static bool operator !(BigNumber A)
        {
            return (A == Zero ? true : (A == Nothing ? true : false));
        }

        /// <summary>
        /// If number is zero or undefined, it is considered <i>Insignificant</i>
        /// </summary>
        /// <returns>True or false</returns>
        public bool IsInsignificant()
        {
            return (!this);
        }

        /// <summary>
        /// Addition
        /// </summary>
        /// <param name="A">First addend</param>
        /// <param name="B">Second addend</param>
        /// <returns>Sum of two given numbers</returns>
        public static BigNumber operator +(BigNumber A, BigNumber B)
        {
            int i, rem = 0;
            BigNumber R = new BigNumber();
            int[] newdig;
            bool incFl = false;

            if (!B) return A.Clone();

            if (A.IsNegative && !B.IsNegative) { return new BigNumber(B - A.Abs()); }
            if (A.IsNegative && B.IsNegative) { R = A.Abs() + B.Abs(); return new BigNumber("-" + R.ToString()); }
            if (!A.IsNegative && B.IsNegative) { return new BigNumber(A - B.Abs()); }

            newdig = new int[System.Math.Max(A.Digits.Count, B.Digits.Count) + 1];
            for (i = 0; i < newdig.Length; i++) newdig[i] = (A.Digits.Count > i ? A.Digits[i] : 0);

            for (i = 0; i < B.Digits.Count; i++)
            {
                if ((B.Digits[i] + newdig[i] + rem) < 10) { newdig[i] += B.Digits[i] + rem; rem = 0; }
                else { newdig[i] += rem + B.Digits[i] - 10; rem = 1; }
            }
            while (rem == 1)
            {
                //if (newdig[i] + 1 >= 10) { newdig[i++] -= 9; rem = 1; } else { newdig[i++]++; rem = 0; }
                incFl = (newdig[i] == 9);
                newdig[i++] += (incFl ? -9 : 1);
                rem = (incFl ? 1 : 0);
                //newdig[i]++;
                //if(newdig[i]>=10) { newdig[i]-=10; rem=1; }
                //else rem=0;
                //i++;
            }

            for (i = 0; i < newdig.Length - (newdig[newdig.Length - 1] != 0 ? 0 : 1); i++) R.Digits.Add(newdig[i]);

            return R;
        }

        private static BigNumber exp(BigNumber A, int range)
        {
            int i;
            BigNumber R = new BigNumber();

            for (i = 0; i < range; i++) R.Digits.Add(0);
            for (i = range; i < A.Digits.Count + range; i++) R.Digits.Add(A.Digits[i - range]);

            return R;
        }

        /// <summary>
        /// Division
        /// </summary>
        /// <param name="A">Nominator</param>
        /// <param name="B">Divisor</param>
        /// <returns>A whole (integer) part of division operation. Reminder is stored in DivReminder property</returns>
        public static BigNumber operator /(BigNumber A, BigNumber B)
        {
            BigNumber Res;
            BigNumber Val = Zero.Clone();
            BigNumber Rem = Zero.Clone();
            int range;
            string rngstr;
            int i;
            bool NegativeResult = false;
            BigNumber X = A.Clone(), Y = B.Clone();

            if (A.IsNegative && !B.IsNegative) NegativeResult = true;
            if (!A.IsNegative && B.IsNegative) NegativeResult = true;

            X = A.Abs();
            Y = B.Abs();
            Res = new BigNumber(X);

            if (X == Y) { Val.DivReminder = Zero.Clone(); return Val; }
            if (Y > X) { Val.DivReminder = X.Clone(); return Val; }
            if (!Y) { throw new Exception("BigNum: Division by Zero!"); }
            if (!X) { return Val; }

            while (!Res.IsNegative && !Res.IsInsignificant())
            {
                if (Res.Digits.Count > Y.Digits.Count + 1)
                {
                    range = Res.Digits.Count - Y.Digits.Count - 1;
                    Rem = Res;
                    Res -= exp(Y, range);
                    rngstr = "1";
                    for (i = 0; i < range; i++) rngstr += "0";
                    if (!Res.IsNegative)
                    {
                        Val += (new BigNumber(rngstr));
                        Rem = Res;
                    }

                }
                else
                {
                    Res -= Y;
                    if (!Res.IsNegative)
                    {
                        Val++;
                        Rem = Res;
                    }
                }
            }

            if (NegativeResult)
            {
                Val.IsNegative = true;
                Rem.IsNegative = true;
            }

            Val.DivReminder = Rem;

            return Val;
        }

        /// <summary>
        /// Multiplication
        /// </summary>
        /// <param name="A">First multiplier</param>
        /// <param name="B">Second multiplier</param>
        /// <returns>Multiplied result</returns>
        public static BigNumber operator *(BigNumber A, BigNumber B)
        {
            BigNumber M1 = new BigNumber(A.ToString());
            BigNumber M2 = new BigNumber(B.ToString());
            BigNumber Val = Zero.Clone();
            BigNumber Jedan = new BigNumber(1);
            int LastDigit;

            if (!A || !B) return Val;

            while (M2.Digits.Count > 0 && !M2.IsInsignificant())
            {
                LastDigit = M2.Digits[0];
                while (LastDigit != 0)
                {
                    Val += M1;
                    LastDigit--;
                    M2 = M2 - Jedan;
                }
                if (M2.Digits.Count > 1)
                {
                    M1 = new BigNumber(M1.ToString() + "0");
                    M2 = new BigNumber(M2.ToString().Substring(0, M2.ToString().Length - 1));
                }

            }

            return Val;
        }


        /// <summary>
        /// Verifies equality between two numbers
        /// </summary>
        /// <param name="A">First number</param>
        /// <param name="B">Second number</param>
        /// <returns>True if numbers are equal, false if not</returns>
        public static bool operator ==(BigNumber A, BigNumber B)
        {
            int i;

            if (A.Digits.Count != B.Digits.Count) return false;
            for (i = 0; i < A.Digits.Count; i++) if (A.Digits[i] != B.Digits[i]) return false;
            return true;
        }

        /// <summary>
        /// Verifies if numbers differ
        /// </summary>
        /// <param name="A">First number</param>
        /// <param name="B">Second number</param>
        /// <returns>True if numbers are different, false if they are equal</returns>
        public static bool operator !=(BigNumber A, BigNumber B)
        {
            int i;

            if (A.Digits.Count != B.Digits.Count) return true;
            for (i = 0; i < A.Digits.Count; i++) if (A.Digits[i] != B.Digits[i]) return true;
            return false;
        }

        /// <summary>
        /// Checks if A &gt;= B
        /// </summary>
        /// <param name="A"></param>
        /// <param name="B"></param>
        /// <returns>True or False</returns>
        public static bool operator >=(BigNumber A, BigNumber B)
        {
            BigNumber C = A - B;
            if (C.IsNegative) return false;
            return true;
        }

        /// <summary>
        /// Checks if A &lt;= B
        /// </summary>
        /// <param name="A"></param>
        /// <param name="B"></param>
        /// <returns>True or False</returns>
        public static bool operator <=(BigNumber A, BigNumber B)
        {
            BigNumber C = B - A;
            if (C.IsNegative) return false;
            return true;
        }

        /// <summary>
        /// Checks if A &lt; B
        /// </summary>
        /// <param name="A"></param>
        /// <param name="B"></param>
        /// <returns>True or False</returns>
        public static bool operator <(BigNumber A, BigNumber B)
        {
            BigNumber C = A - B;
            if (C.IsNegative) return true;
            return false;
        }

        /// <summary>
        /// Checks if A &gt; B
        /// </summary>
        /// <param name="A"></param>
        /// <param name="B"></param>
        /// <returns>True or False</returns>
        public static bool operator >(BigNumber A, BigNumber B)
        {
            BigNumber C = B - A;
            if (C.IsNegative) return true;
            return false;
        }

    }
}
